The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
52 views
Show that the following language is not regular.

$L=$ {$a^nb^k:n>k$} $\cup$ {$a^nb^k:n\neq k-1$}.
in Theory of Computation by Boss (15k points) | 52 views

1 Answer

0 votes

In both the given regular expressions, we need to count the number of a's and number of b's to check the given conditions, which cannot be implemented by a DFA/NFA. So they are not regular languages and the Union of these two languages is also not regular.

We need to use PDA.

by Junior (551 points)

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,309 questions
55,743 answers
192,226 comments
90,495 users