Skip to main content
Share Your Experience: Take the 2024 Developer Survey
Pratik Hadawale's user avatar
Pratik Hadawale's user avatar
Pratik Hadawale's user avatar
Pratik Hadawale
  • Member for 2 years
  • Last seen more than 1 year ago
4 votes
4 answers
5k views

What exactly is pumping length in pumping lemma?

3 votes
1 answer
1k views

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

3 votes
2 answers
99 views

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

2 votes
2 answers
177 views

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

1 vote
1 answer
590 views

Converting Regular Expression to Finite Automata

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?

1 vote
1 answer
310 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
451 views

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

1 vote
2 answers
170 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?

1 vote
1 answer
291 views

Converting Deterministic Finite Automata to Regular Expression

0 votes
1 answer
37 views

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

0 votes
1 answer
59 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
0 answers
85 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?

0 votes
2 answers
66 views

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

0 votes
1 answer
68 views

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

0 votes
2 answers
176 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?

0 votes
1 answer
54 views

Does every regular expression describe only 1 language?

0 votes
1 answer
63 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
429 views

Conversion of epsilon NFA to DFA, handling epsilon transitions

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
1 answer
1k views

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

0 votes
0 answers
118 views

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

0 votes
1 answer
552 views

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

0 votes
1 answer
283 views

Confusion regarding the intuition behind epsilon transition in NFA

0 votes
1 answer
2k views

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

-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

-2 votes
1 answer
121 views

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