reshown by
317 views
1 votes
1 votes

Consider the statements:
S1: Regular Expression for the language over the alphabet Σ={a} containing strings whose length is either multiple of 2 or a multiple of 3 (this includes the empty string) is (aa+aaa)*
S2: If L={0m 1n│m≥n and m-n is even} is a Context free language 
Which of the above statements are TRUE?

reshown by

1 Answer

Best answer
0 votes
0 votes
First statement is wrong because it is also have a string  "aaaaa" which is not divisible by 2 or 3 .

Second is right because we can make PDA for given language so this is CFL .

For making PDA we first push all m 0's and pop with n 1's after that in stack m-n 0's remains.

After we pop the 0's from stack and make a mod loop (like dfa ) so we can check remain 0's are even or odd.
selected by

Related questions

0 votes
0 votes
1 answer
1
Lone Wolf asked Aug 7, 2018
175 views
is grammar CFG = S->AS/epsilon A->aA/ain Chomsky Nomal form ?
0 votes
0 votes
2 answers
2
1 votes
1 votes
1 answer
3
0 votes
0 votes
3 answers
4
Anmol Verma asked Nov 30, 2016
2,204 views
S->AbaCA->BCB->b/epsilonC->D/epsilonD->d I want to know that will A contain epsilon as B and C both are null variables???(In Elimination of epsilon-production)