Recent questions tagged context-free-language

0 votes

0 answers

1

Context Free Grammar
Consider the following CFG 'G' S--> aA/bSS/SS A--> aAb/bAa/AA/ε The language generated by G is: a)Set of all strings with atleast one 'a' b)Set of all strings with atleast two a's c)Set of all strings with atleast one more 'a' than number of b's d)None of these

asked 1 day ago in Theory of Computation by Sambhrant Maurya Junior (757 points) | 17 views

0 votes

1 answer

2

Theory of Computation
$L1= \left \{ a^m b^n c^n d^m | m \neq n \right \}$ $L2= \left \{a^i b^j c^k | (i<=j)or (j<=i), j=k \right \}$ $L3= \left \{a^i b^j c^k| i=j, j<k \right \}$ The number of the above languages that are context free are ?

asked 2 days ago in Theory of Computation by Priyam Pandey (61 points) | 66 views

0 votes

0 answers

3

CFL with Empty Stack or Final State
$1)$"We can solve same PDA with empty stack and using final state" Can give an example of such language? Where is the difference between solving a pda with empty stak and by accepting final state? I got this link but without ... -acceptance-by-empty-stack-and-final-state $2)$If language has prefix property, why it cannot be solved with empty stack?

asked Oct 4 in Theory of Computation by srestha Veteran (98.5k points) | 45 views

0 votes

0 answers

4

self doubt
name and explain the language which are context free,context sensitive i.e. FORTRAN is CSL, now tell me about c,cobol,c++,java and any other language which you can explain etc https://gateoverflow.in/80293/gate1987-1-xiii

asked Sep 30 in Theory of Computation by Gurdeep Saini Junior (829 points) | 12 views

0 votes

0 answers

5

CFG-Doubt
$L=a^mb^nc^pd^q | m+p=n+q, m,n,p,q>=0$ is the language CFG or CFL?

asked Sep 26 in Theory of Computation by aditi19 Junior (863 points) | 30 views

0 votes

0 answers

6

Context free languages
X belongs to {a,b}* such that n(a)<n(b)<2n(a) is a CFL. Please somebody explain the push and pop sequences of the alphabets on the stack. I'm not being able to visualise, how it is CFL?

asked Sep 18 in Theory of Computation by aambazinga Active (1.2k points) | 11 views

+1 vote

0 answers

7

Michael sipser
I read this excerpt from sipser book- We write a,b → c to signify that when the machine is reading an a from the input, it may replace the symbol b on the top of the stack with a c. Any of a, b, and c may be ε. If a is ε, the machine ... using any stack symbol as written here that top of stack might be epsilon if we don't want to consume it. If someone can clear my doubt. Thanks

asked Sep 15 in Theory of Computation by sushmita Boss (14.7k points) | 10 views

0 votes

0 answers

8

Closure Property
If L1 is CSL and L2 is CFL, then which of the following is correct ? A.L1' - L2 is CSL always B. L1 - L2' is CSL always C. L1 intersection Regular is Regular always D. L1.L2 is CSL but not CFL

asked Sep 9 in Theory of Computation by Na462 Loyal (6.5k points) | 69 views

0 votes

0 answers

9

peter linz
The language L1={a^n b^n} union {b} The language L2={a^n b^n} union {a} They both are deterministic CFL. Am i right?

asked Sep 9 in Theory of Computation by sushmita Boss (14.7k points) | 36 views

0 votes

0 answers

10

self doubt
Consider the Context free language which has equal no of as and bs. eg- abab Since a proper prefix ab also belongs to this language, this language does not satisfy prefix property as far as i understand. But we can clearly draw a deterministic PDA ... with empty stack for CFL without prefix property. But above example forms a contradiction. Please resolve my doubt. I am getting confused.

asked Sep 8 in Theory of Computation by sushmita Boss (14.7k points) | 53 views

0 votes

0 answers

11

PDA-Doubt
L=$a^mb^n$ | m!=n is the following DPDA correct for the mentioned language?

asked Sep 3 in Theory of Computation by aditi19 Junior (863 points) | 23 views

0 votes

0 answers

12

Doubt-PDA
what is the PDA for {L=$a^mb^n$ |m>n}

asked Sep 2 in Theory of Computation by aditi19 Junior (863 points) | 66 views

0 votes

1 answer

13

Non inherently ambiguous

asked Sep 2 in Theory of Computation by Na462 Loyal (6.5k points) | 35 views

0 votes

0 answers

14

Parsing
For a grammar to be LR(k), it should have a PDA? Like a DPDA or just PDA in general?

asked Aug 31 in Compiler Design by Mizuki Junior (839 points) | 28 views

0 votes

0 answers

15

DPDA acceptance by empty stack
Is this approach of acceptance by empty stack correct ? I am confused because i have read that acceptance by empty stack may not be able to accept all regular languages.

asked Jul 28 in Theory of Computation by Matrix (63 points) | 40 views

+1 vote

2 answers

16

Languages
Consider a language over Σ={a,b} the description of L is given below. L={ PQ | P ∈(a,b)* , Q ∈ (a,b)* and na(P) = nb(Q) }. Select the correct option. 1. L is DCFL but not regular. 2. L is CSL but not CFL. 3. L is CFL but not DCFL. 4. None of these.

asked Jul 3 in Theory of Computation by Priyansh Singh (155 points) | 104 views

0 votes

1 answer

17

self made doubt
How to know that the language needs 1 stack or more than one stack in order to know about it is regular, context-free or not. example L1={$a^i b^j c^k│i<j<k$} L2={$a^i b^j c^k│i<j \ or \ k<j$} L3={$a^i b^j c^k│i<j \ and \ k<j$}

asked Jun 11 in Theory of Computation by Divyanshum29 Junior (567 points) | 68 views

0 votes

2 answers

18

Theory Of Computation Doubt.
I saw some where that a language which accepts $a^{n^{2}} | n \geq1$ is not context free Language and not regular language. is it not a language that has at least one $'a'$ as the string?. It should be regular as well according to this Logic right. Please correct me if wrong.

asked Jun 3 in Theory of Computation by abhiram144 (63 points) | 53 views

0 votes

2 answers

19

Ambiguous and unambiguous grammar
If a grammar( $CFG$ ) has more than one Right most derivation, Can it be called ambiguous ? Or we say a grammar is ambiguous only when it has more than one left most derivation ?

asked May 28 in Compiler Design by Rahul Ranjan 1 (151 points) | 68 views

+2 votes

2 answers

20

Grade up topicwise questions
L1={a^n b^n c ^m|m>=0 and n>=0} L2={a^m b^ n c^ n|n>=0 and m>=0} If L3=L1UL2 then how many of L1,L2,L3 are context free languages? A)1 (B)2 (C)3 (D) none Answer given option C. Please explain?

asked May 8 in Theory of Computation by Sona Barman Active (1.2k points) | 123 views

0 votes

4 answers

21

Context Free Language
L= { $a^{n}b^{m}$ | $n<=m<=2n$ } a) DCFL b) CFL but not DCFL c) Not CFL

asked May 6 in Theory of Computation by Subham Nagar Junior (679 points) | 155 views

+1 vote

1 answer

22

which of the following statements are correct in context of LR parser ?

asked Apr 30 in Compiler Design by radha gogia Loyal (7.5k points) | 63 views

0 votes

1 answer

23

Context Free Languages
Answer with explanation will be acknowledged.

asked Apr 13 in Theory of Computation by Subham Nagar Junior (679 points) | 64 views

0 votes

1 answer

24

Introduction to Computer Theory
Give CFG for the following language L =$ {(a^{m})(b^{m+n})(c^{n}) | m,n= 0,1,2,.....}$

asked Apr 12 in Theory of Computation by The Capricorn (147 points) | 57 views

0 votes

1 answer

25

Exam - Foundation of Computing - 2018
Find a context-free grammar for the following language: L = { a^m b^m c^k | k <= m } (in order to show that the language is context-free)

asked Apr 11 in Theory of Computation by Melissa (7 points) | 45 views

+1 vote

0 answers

26

whether the given languages are context free or not

asked Apr 8 in Theory of Computation by Sambit Kumar Active (4.1k points) | 101 views

+2 votes

0 answers

27

Theory of computations(CFG)
$L1$ has the following grammar:- $S \rightarrow aB/BA$ $A\rightarrow bAA/aS/a$ $B\rightarrow b/bS/aBB$ can someone help me with an easy way to get the general expression for string belonging to this language. Or some hint that how should I proceed to solve this question.

asked Mar 29 in Theory of Computation by hrcule (287 points) | 50 views

+4 votes

1 answer

28

Context Free Languages
Which of these languages are deterministic? $L_{1} =$ $\left \{a^{n}b^{n}: n \geq 1 \right \}\cup \left \{ b \right \}$ $L_{2} =$ $\left \{a^{n}b^{n}: n \geq 1 \right \}\cup \left \{ a \right \}$

asked Mar 28 in Theory of Computation by Mk Utkarsh Boss (20.2k points) | 135 views

+2 votes

0 answers

29

CFG to GNF
Convert the given CFG to GNF. $S \rightarrow MN$ $M\rightarrow aMb|\epsilon $ $N\rightarrow aNb|\epsilon $

asked Mar 25 in Theory of Computation by Mk Utkarsh Boss (20.2k points) | 166 views

0 votes

0 answers

30

Peter Linz Exercise 6.1.9
Eliminate all unit-productions from the grammar $S \rightarrow a | aA| B|C,$ $A \rightarrow aB | λ,$ $B \rightarrow aA,$ $C \rightarrow aCD,$ $D \rightarrow ddd $

asked Mar 23 in Theory of Computation by Mk Utkarsh Boss (20.2k points) | 70 views

tags	tag:apple
author	user:martin
title	title:apple
content	content:apple
exclude	-tag:apple
force match	+apple
views	views:100
score	score:10
answers	answers:2
is accepted	isaccepted:true
is closed	isclosed:true

Recent questions tagged context-free-language

Recent Posts

Recent Blog Comments