Give context-free grammars that generate these languages

143 Views Asked by At

Give context-free grammars that generate these languages

  1. {a^(2i) b^(3k) c^(4i) | i => 1, k => 1}

  2. {a^(i) b^(k) c^(k) a^(i) | i => 1, k => 1}

I am seriously stuck here. Esp for the 1st one. For the 2nd question, I say S -> abSca but the string won't get concatenated the same way, so can I do:

S -> TST T -> a S -> bc

1

There are 1 best solutions below

1
On BEST ANSWER

For the first language:

$$S\to aaScccc~|~aaBcccc$$ $$B\to bbbB~|~bbb$$

  1. From the first rule you make sure that words start with $a^{2i}$, with $i\geq 1$. Also, you make sure that for each two $a$'s in the front of a word, there will be 4 $c$'s in the end of the word.
  2. From the second rule, you make sure that between $a$'s and $c$'s, there will be a multiple of 3 occurrences of $b$.

For the second language:

$$S\to aBa~|~aSa$$ $$B\to bBc~|~bc$$

  1. From the first rule you make sure that there is the same number of $a$'s at the start and the end of a word.
  2. From the second rule you make sure that between the $a$'s at the start and the end of the word, there will be the same number of $b$'s and $c$'s.

Your rules for the second language are not correct, because from rule $S\to abSca$, you get $i=k$, which is not a condition for the words of the language. I mean, the language contains also words for which $i\neq k$. Not to mention that with this rule only, you'll never produce any word, because you'll always loop from $S$ to $S$. You need a string with only terminal symbols so that the production of a word terminates in a finite number of steps.

Also, with the other rules you wrote ($S\to TST$, $T\to a$ and $S\to bc$), the only word you can produce is $abca$ and nothing else.