Programming

16781 readers

117 users here now

Welcome to the main community in programming.dev! Feel free to post anything relating to programming here!

Cross posting is strongly encouraged in the instance. If you feel your post or another person's post makes sense in another community cross post into it.

Hope you enjoy the instance!

Rules

Follow the programming.dev instance rules
Keep content related to programming in some way
If you're posting long videos try to add in some form of tldr for those who don't want to watch videos

Wormhole

Follow the wormhole through a path of communities [email protected]

founded 1 year ago

MODERATORS

[email protected]

[CompSci] All regular languages can be constructed from performing operations on elementary languages? (lemy.lol)

submitted 5 months ago* (last edited 5 months ago) by [email protected] to c/[email protected]

2 comments fedilink hide all child comments

While learning Automata and computation theory independently, I made a realization I want to confirm.

Regular languages can all be created by taking elementary languages (languages made up of a single member of its alphabet) and performing closed operations in them, such as union, concat, and kleene star. This was clear to me from regular expressions.

Is this true? Is there any significance to this fact?

What about Context-free languages and other formal languages? Are there operations that can be performed on elementary languages to create all of them? Or is this a special property of regular languages only?

top 2 comments

sorted by: hot top controversial new old

[–] [email protected] 5 points 5 months ago

You are correct. For the example of regular languages, we have Kleene algebras, which are special cases of *-semirings. Similar algebras exist for the rest of the Chomsky hierarchy.

Before going up the hierarchy, I would recommend checking out what we can do with semirings alone. Two great papers on the topic are "Fun with Semirings", Dolan 2013 and "A Very General Method of Computing Shortest Paths", O'Connor 2011. Don't be fooled by the titles; they both involve surprise guest appearances from regular expressions.

[–] [email protected] 2 points 5 months ago

If I can remember my theory correctly the difference between languages revolves around the machinery required to recognize the language.

Regular expressions can be recognized with just finite state machines (NFA or DFA have the same power).

Context free languages require a Push down automata. And context sensitive languages need a Turing Machine.

When looking at regular expressions as NFAs you can see the operations you mentioned.

Concat a b: is just state transition

Union a b: have an epsilon transition from the start state to an NFA for a and one into the NFA for b

Repeat a: add an epsilon transition from the accept state of a to it's own start state

With the more powerful grammars you might be able to do similar analysis on the ability to join machines together but it's been too many years since I did any formal work like that.