Episode #125 of the Stack Overflow podcast is here. We talk Tilde Club and mechanical keyboards. Listen now

Tag Info

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