edited by
1,116 views
1 votes
1 votes

The language $L =\{a^i \: b \: c^i \mid i \geq 0\}$ over the alphabet $\{a, b, c\}$ is

  1. regular language
  2. Not a deterministic context free language but a context free language
  3. Recursive and is a deterministic context free language
  4. Not recursive
edited by

1 Answer

0 votes
0 votes

L ={ab ci| i ≥ 0} 

Given language has equal number of a in the beginning as the number of c in the end which makes it context free language.

Simultaneously, they are separated by b which makes the language deterministic.

So, the language is DCFL and as DCFL is the subset of recursive languages it is recursive too.

Option (C)

Answer:

Related questions

2 votes
2 votes
2 answers
1
Arjun asked Nov 5, 2017
1,810 views
Finite state machine can recognize language generated by _________Only context free grammarOnly context sensitive grammarOnly regular grammarAny unambiguous grammar
2 votes
2 votes
1 answer
2
Arjun asked Nov 5, 2017
1,169 views
Which of the following problems is undecidable?To determine if two finite automata are equivalentMembership problem for context free grammarFiniteness problem for finite ...
1 votes
1 votes
2 answers
3
Arjun asked Nov 5, 2017
2,048 views
Pumping lemma for regular language is generally used for provingWhether two given regular expressions are equivalentA given grammar is ambiguousA given grammar is regular...
5 votes
5 votes
1 answer
4
Arjun asked Nov 5, 2017
1,530 views
The logic of pumping lemma is an example of _________IterationRecursionThe divide and conquer principleThe pigeon – hole principle