Context Sensitive Grammar and Language || Lesson 79 || Finite Automata || Learning Monkey ||

แชร์
ฝัง
  • เผยแพร่เมื่อ 27 ม.ค. 2022
  • Context Sensitive Grammar and Language
    In this class, We discuss Context Sensitive Grammar and Language.
    The reader should have prior knowledge of context-free grammar. Click Here.
    In our previous classes, we discussed regular grammar.
    The language aⁿbⁿ can not be defined using regular grammar.
    Similarly, the language aⁿbⁿcⁿ can not be defined using context-free grammar.
    Yes, we can define the language aⁿbⁿcⁿ using context-sensitive grammar.
    Given grammar G = (V, T, P, S)
    The production conditions are different from regular and context-free grammar.
    Production Conditions:
    1) Take a production X - Y
    X, Y belongs to (V U T)^+
    X, Y is a string of terminals and non-terminals.
    The symbol + says at least one symbol considered.
    From the first condition, we understand epsilon is not present in the production.
    Context-sensitive grammar does not allow epsilon in the language.
    2) |X| = |Y|
    The length of the left side production should be less than or equal to the length of the right side of the production.
    Example: aAb - abb
    aAc - abcD
    aA - c
    The last production is not context-sensitive grammar because the length of the left side is greater.
    Why is the name context sensitive?
    Example:
    aAb - aaa
    aA - b
    We are applying A based on the Context.
    We define the production Based on the before and after symbol.
    If the before symbol is a and the after symbol is b, we apply aaa.
    We do not consider the Context in a context-free grammar.
    A - aA | aB
    Whenever we see production A, we apply.
    CFG is a subset of context-sensitive grammar.
    Assumption: epsilon not in language.
    The production condition of CFG is one condition in Context-sensitive grammar.
    The below venn diagram shows the acceptance of languages.
    Link for playlists:
    / @learningmonkey
    Link for our website: learningmonkey.in
    Follow us on Facebook @ / learningmonkey
    Follow us on Instagram @ / learningmonkey1
    Follow us on Twitter @ / _learningmonkey
    Mail us @ learningmonkey01@gmail.com

ความคิดเห็น • 16

  • @forkids8773
    @forkids8773 2 ปีที่แล้ว +1

    Really useful for me. Well done

  • @pawanpt2682
    @pawanpt2682 3 หลายเดือนก่อน

    Sir is it possible that in production only left context is available or only right context is available?

  • @faizalmakhrus8645
    @faizalmakhrus8645 ปีที่แล้ว

    Superb 👍🏻

  • @thedarkstar07
    @thedarkstar07 11 หลายเดือนก่อน

    yeah understood clearly 🤗😅

  • @ulhass6377
    @ulhass6377 23 วันที่ผ่านมา

  • @pawanpt2682
    @pawanpt2682 หลายเดือนก่อน

    Sir what is one sided context grammar?

  • @abhisheksambyal
    @abhisheksambyal ปีที่แล้ว

    bro what if only terminal symbol in LHS

    • @LearningMonkey
      @LearningMonkey  ปีที่แล้ว

      Yes u can use them according to ur need

  • @anantshelgaonkar3950
    @anantshelgaonkar3950 ปีที่แล้ว

    Name of your channel is very funny sir.

  • @pawanpt2682
    @pawanpt2682 3 หลายเดือนก่อน

    Sir
    1.......A->bc and aB->Ca is context sensitive or not?
    2.......bB->bb is context sensitive or not?

    • @LearningMonkey
      @LearningMonkey  3 หลายเดือนก่อน

      Yes 1 and 2 are context sensitive

  • @mgemov
    @mgemov ปีที่แล้ว

    ye