The Gateway to Computer Science Excellence
0 votes
21 views

Let $CFG$   $G$ be the following grammar$.$

  •  $S\rightarrow aSb \mid bY \mid Y a$
  • $Y\rightarrow bY \mid aY \mid \epsilon$

Give a simple description of $L(G)$ in English$.$ Use that description to give a $CFG$ for $\overline{L(G)},$ the complement of $L(G).$

in Theory of Computation by Veteran (60.8k points)
edited by | 21 views
0
L(G)=$a^nxb^n$ | $x\epsilon (a|b)^+$

Please log in or register to answer this question.

Related questions

Quick search syntax
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
50,833 questions
57,750 answers
199,479 comments
108,159 users