Skip to main content
Pratik Hadawale's user avatar
Pratik Hadawale's user avatar
Pratik Hadawale's user avatar
Pratik Hadawale
  • Member for 2 years, 1 month
  • Last seen more than 1 year ago
5 votes
4 answers
6k views

What exactly is pumping length in pumping lemma?

1 vote
1 answer
4k views

Why L1 := { a^n b^m | m, n ≥ 0 and m ≥ n } is regular and L2 := { a ^ n b ^ n | n>= 0 } not regular?

0 votes
1 answer
2k views

When is a grammar ambiguous or When is a grammar not ambiguous?

3 votes
1 answer
1k views

When converting a epsilon NFA to NFA to DFA, how to handle the start state?

0 votes
1 answer
1k views

How to prove ww^r is context free using pumping lemma for context free languages

1 vote
1 answer
601 views

Converting Regular Expression to Finite Automata

0 votes
1 answer
570 views

When converting from nfa to dfa, do we always ignore the trap state?

1 vote
1 answer
472 views

Confusion regarding "epsilon" transition in NFAs, whether taking epsilon before or after reading the input affects the final states

0 votes
1 answer
432 views

Conversion of epsilon NFA to DFA, handling epsilon transitions

1 vote
1 answer
317 views

Is Enumerator a variant of Turing machine that starts with empty string and builds according to the description of language

1 vote
1 answer
296 views

Converting Deterministic Finite Automata to Regular Expression

0 votes
1 answer
293 views

Confusion regarding the intuition behind epsilon transition in NFA

1 vote
2 answers
188 views

Why does Michael Sipser state that $0^p0^p$ is a bad choice for proving $L=\{ww|w \in \{0,1\}^*\}$ is non-regular a bad choice?

2 votes
2 answers
180 views

Is ε a part of alphabet or property of alphabet and NFA in FA

0 votes
2 answers
179 views

When applying pumping lemma to prove that a language is not regular, do we need to apply it to all decompositions of a string or just one?

-2 votes
1 answer
124 views

How to cross verify the resultant E-NFA in "Regular Expression to E-NFA" is correct?

0 votes
0 answers
118 views

Is this how Interval Partitioning Problem aka interval graph coloring problem works?

3 votes
2 answers
108 views

Implementation details of "transitions" of Non-deterministic push-down automata

0 votes
3 answers
107 views

Can we further minimize this regular expression: a*(ac* + bc* + cc* + b*bc* + b*cc* ) + b*(bc* + cc*) + c*

0 votes
0 answers
87 views

What should be the order of eliminating empty rules and unit rules when converting context free grammar to chomsky normal form?

0 votes
1 answer
78 views

Let $L$ the language over $\{a,b\}$ of words that contains the same number of occurrences of $a$ and $b$. Which of the following languages is regular?

-1 votes
3 answers
72 views

Is it possible to divide a string, according to pumping lemma, from a language in a way that pumping a section would render the language -non regular

0 votes
1 answer
69 views

In Context free languages, is it okay to substitute multiple same variables at the same time?

0 votes
2 answers
68 views

How can a $P(n)$ run in polynomial time if it calls $R(m)$ which has exponential time

0 votes
1 answer
66 views

When converting DFA/NFA to regular expression, where the DFA/NFA accepted empty string, is it okay to not have empty string as kleene star?

0 votes
1 answer
62 views

When applying pumping lemma for regular languages to prove that a given language is non regular, do we show that pumping fails for all $i$ or one $i$?

0 votes
1 answer
58 views

Does every regular expression describe only 1 language?

0 votes
1 answer
40 views

Do Left regular grammar describe a language containing the reverse of the strings described by the right regular grammar for another language?