edited by
887 views
3 votes
3 votes

Sorry my BAD, it's an infinite language!

The given set {1, 101, 11011,1110111,......} is a Regular Language or CFL?

edited by

2 Answers

Best answer
3 votes
3 votes
The language is L = {$1^{n}01^{n} \dotplus 1$, n>=1}

Notice here we need to check number of 1's before 0 is equal to number of 1's after zero. Which we can not achieve by DFA. So it is not regular.
This language is CFL as well as DCFL, At start we push all the 1's onto the stack, when we see 0 we ignore and after every 1 we pop 1's from the stack, if we end up with empty stack, we accept this language. So it is CFL as well as DCFL
selected by
3 votes
3 votes

By just looking at the kind of strings enumerated by the language, one can be under the impression that it is a CFL as it generates palindromes.

But the given language is finite and any finite language is always regular.

Related questions

0 votes
0 votes
1 answer
1
gateexplore asked Jun 11, 2023
411 views
Construct an NFA that will accept string of 0's, 1's and 2's beginning with a 0's followed by an odd number of 1's and ending with any number of 2's. Please give the answ...
3 votes
3 votes
1 answer
2
abhinowKatore asked Jan 14, 2023
530 views
Please explain what is difference between $\overline{L(N)}$ and $L(\overline{N}$) ?
0 votes
0 votes
1 answer
3
atulcse asked Jan 21, 2022
829 views
Given a CFG and a string, what is the relation between the number of leftmost derivations, the number of rightmost derivations and the number of parse trees?
3 votes
3 votes
2 answers
4
Hirak asked May 22, 2019
2,306 views
How many 2 state DFA’s with designated initial state can be constructed over the alphabet Σ = {a, b} that accept empty language ϕ ?(a) 4 (b) 16 (c) 20 ...