2
Our grammar $G$ has following two production where $S$ is start symbol.
$S\rightarrow aTbS \vert\epsilon$
$T\rightarrow aTb|\epsilon$
Now to convert it to chomsky normal form (CNF) we have to perform following steps:
If there is some production having $S$ in it's right side($S\rightarrow aTbS$ in this example) then add new start symbol $S_0$ and ...
2
Your approach won't work. Whenever you try to match the length of two non-terminals, that should be a big red flag your approach won't work.
Here's a hint: expand from the middle out, after starting with $S = a \mid b \mid aAa \mid bBb$. Can you take it from here?
2
Equal numbers of a’s on either side, then the middle is replaced by a+b or by ba+.
2
The idea is to start with a grammar for the related language $L'_2 = \{a^ib^j \mid 2j \leq i \leq 3j\}$:
$$ S \to a^2Sb \mid a^3Sb \mid \epsilon. $$
We want to force at least one production of the form $a^2Sb$ and at least one of the form $a^3Sb$. There are many ways of doing that. The simplest, probably, is to force one of these productions to be the first, ...
2
Any regular language upholds the pumping lemma. Hence, if a language doesn't uphold the pumping lemma, it is not a regular language. This is in fact the standard way of proving a language is not regular.
Let us choose $p$ to be the pumping length. Let's now take $0^n=1^n \oplus 1^n$, which is in $A$. This string can be decomposed into three concatenated ...
1
If you give a word $w$ not in the language, then the TM is not guaranteed to halt as an NPDA isn't always guaranteed to terminate in finite steps for a finite word.
So, you can produce a counter example in which your construction doesn't work. Take an NPDA which doesn't terminate for a given word (exists, of course) and run your algorithm on that word. ...
Only top voted, non community-wiki answers of a minimum length are eligible
