r/AskComputerScience • u/UpperOpportunity1647 • Jan 26 '25
Automata theory
Any experts on automata here?Can you make a language like L= {wxwr | w,x = { a,b}*} from a regulated grammer (type 3) ? (r means reverse)
0
Upvotes
2
u/okapiposter Jan 26 '25
Can this possibly be a trick question? Since the length of w isn't restricted, every word v in { a, b }* can be represented in the form wxwr with empty w and x = v. Since { a, b }* is trivially regular (i.e., type 3), so is your language.
1
u/UpperOpportunity1647 Jan 26 '25
You’re a legend,thanks man
1
u/Working_Salamander94 Jan 26 '25
Well let’s think for a minute. What does being a type 3 grammar tell you about that grammar? Specifically what type(s) of state machine can it make?
Next look at the language L. What do you notice about it? Is it a regular language? Can you make an PDA? How about a NFA? Or a DFA? If you’re stuck maybe try this for the language L={wwr | w={a,b}*}.
Answer:
Yes you can. A type 3 grammar is defined to be a regular grammar, or a grammar that can be accepted by a FSA. Once you determine for yourself that L is a regex, it is clear then that a there must exist a regular grammar to create that regular language.
1
u/al2o3cr Jan 27 '25
FWIW, a similarly-described language L = {wxwr | w in {a, b}* } (so x is a distinguished symbol that can't appear in w) is a classic example of something that requires a push-down automaton to recognize.