0
$\begingroup$

I have two grammars:

 L → ε | aLcLc
 L → ε | aLcLc | LL 

This two grammars are equals but the first one is regular, so it produces a regular language and a Finite State Automata. Instead, the second one is non regular but it might produces a regular language.
To prove it, I want to create two differentes automata: the first one should be a correct automata and if the second one can't be create then the language is not regular. Are all this statments correct?
If so, can someone help me build these two automata? Thank you!

$\endgroup$
4
  • 2
    $\begingroup$ Neither of your grammars are regular, I'm afraid. And they also don't produce regular languages. $\endgroup$
    – dkaeae
    Aug 23, 2019 at 15:34
  • $\begingroup$ @dkaeae sorry, you're right. Nothing bad though. How did you understand that they don't produce regular languages? That's my problem. Thank you. $\endgroup$
    – cieco1109
    Aug 23, 2019 at 15:51
  • 1
    $\begingroup$ Intuitively, you can see the words are such that $2|w|_a = |w|_c$, and, as the folklore has it, "DFAs can't count". Here is a list of techniques for actually proving it. $\endgroup$
    – dkaeae
    Aug 23, 2019 at 15:57
  • $\begingroup$ Thank you, I am reading it. If I want use pumping lemma, I should convert the grammar into a language (for example L={ (01) n2n ∣ n≥0}. Is it right? How do I convert the second grammar? I don't see rules to follow. can you give me a suggestion? $\endgroup$
    – cieco1109
    Aug 23, 2019 at 16:17

1 Answer 1

1
$\begingroup$

Your first language isn't regular. Here is a simple way of showing this. Consider all words in your language of the form $a^*c^*$; if your language were regular, then so would be that language. However, the new language is generated by the grammar $L \to \epsilon \mid aLcc$ (this requires an argument), and so is $\{a^n (cc)^n : n \geq 0\}$, which is classically known to be irregular.

With more effort, you can show that your language consists of all words $w$ in which every proper prefix $x$ satisfies $\#_a(x) > 2\#_c(x)$, and furthermore $\#_a(w) = 2\#_c(w)$.

An identical argument works for your second language. With more effort, you can show that the language consists of all words $w$ in which every prefix $x$ satisfies $\#_a(x) \geq 2\#_c(x)$, and furthermore $\#_a(w) = 2\#_c(w)$.

Summarizing, both of your languages are irregular, and this can be shown by intersecting them with $a^*c^*$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.